% !TEX TS-program = pdflatex
% !TEX encoding = IsoLatin
\documentclass[french,11pt,twoside]{report}
\usepackage[T1]{fontenc}
\usepackage[utf8]{inputenc}
\usepackage[letterpaper]{geometry}
\geometry{verbose,tmargin=2.5cm,bmargin=2.5cm,lmargin=2.5cm,rmargin=2.5cm}
\usepackage{float}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{esint}
\usepackage{fancyhdr}
\usepackage{setspace}
\usepackage{ulem}
\usepackage{graphicx}
\usepackage{amsmath}  \newtheorem{de}{Définition}[subsection] \newtheorem{theo}{Théorème}[section]  \newtheorem{prop}[theo]{Proposition} 
\usepackage[mathscr]{euscript}
\usepackage{tabularx}
\usepackage{eso-pic}
\usepackage{xcolor}
\usepackage{color}
\usepackage[colorlinks,linkcolor=black]{hyperref}
\usepackage[center]{caption}
\usepackage[frenchb]{babel}

\frenchbsetup{StandardItemLabels,CompactItemize=false}
 % permet d'obtenir les listes bullet point meme avec le package french babel,ReduceListSpacing=false

%pour ne pas avoir de chapitre:
\makeatletter 
\renewcommand\thesection{\@arabic\c@section} 
\makeatother


\makeatletter
\def\clap#1{\hbox to 0pt{\hss #1\hss}}
\def\ligne#1{
\hbox to \hsize{
\vbox{\centering #1}}}
\def\haut#1#2#3{%
\hbox to \hsize{%
\rlap{\vtop{\raggedright #1}}
\hss
\clap{\vtop{\centering #2}}
\hss
\llap{\vtop{\raggedleft #3}}}}
\def\bas#1#2#3{
\hbox to \hsize{
\rlap{\vbox{\raggedright #1}}
\hss
\clap{\vbox{\centering #2}}
\hss}
\llap{\vbox{\raggedleft #3}}}
\def\maketitle{
\thispagestyle{empty}\vbox to \vsize{%
\haut{}{\@blurb}{}
\vfill
\vspace{1cm}
\begin{flushleft}
\usefont{OT1}{ptm}{m}{n}
\huge \center \@title
\end{flushleft}
\par
\vspace{0.5cm}
\hrule height 1pt 
\par
\begin{flushright}
\usefont{OT1}{phv}{m}{n}
\Large \center \@author
\par
\end{flushright}
\vspace{1cm}
\vfill
\vfill
\bas{}{\@bla}{}
}%

}
\def\date#1{\def\@date{#1}}
\def\author#1{\def\@author{#1}}
\def\title#1{\def\@title{#1}}
\def\location#1{\def\@location{#1}}
\def\blurb#1{\def\@blurb{#1}}
\def\bla#1{\def\@bla{#1}}
\date{24 février 2013}
\author{}
\title{}
\location{Paris}\blurb{}
\makeatother
\title{\large{\textbf{}}  \\ \huge{\textsc{K-Means Clusturing et Multithreading }}}
\author{\small{Gilles Drigout, Hugo Bompard }}
\location{Paris}
\blurb{%
\large{\textsc{École Nationale de la Statistique et de l'Administration Économique}}
}%
\bla{%
\large{Projet d'informatique -- C$\#$ }
}%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% racourcis 

\def\R{\mathbb{R}} %ensemble des réels
\def\C{\mathbb{C}} %ensemble des complexes
\def\K{\mathbb{K}} %corps des réels ou complexes
\def\N{\mathbb{N}} %ensemble des entiers naturels
\def\Z{\mathbb{Z}} %ensemble des entiers relatifs
\def\Q{\mathbb{Q}} %ensemble des rationnels
\def\E{\mathbb{E}} %espérance mathématique
\def\V{\mathbb{V}} %variance mathématique
\def\P{\mathbb{P}} %probabilité
\def\Norm{\mathcal{N}} %Loi normale
\newcommand{\loinormale}[2]{\mathcal{N}(#1,#2)} % Loi normale de moyenne #1 et de variance #2
\def\combi{\mathrm{C}} %nombre de combinaisons
\def\diff{\,\mathrm{d}} %différentielle
\def\arrange{\mathrm{A}} %nombre d'arrangements
\def\tr{\mathrm{Tr}} %trace
\def\rg{\mathrm{Rg}} %rang
\def\Score{\mathrm{Score}} %score
\def\Cov{\mathrm{Cov}} %covariance
\def\var{\mathrm{V}_{Emp}} %variance empirique
\newcommand\ds{\displaystyle{}}
\renewcommand\arctan{\mathrm{Arctan}}
\renewcommand\arcsin{\mathrm{Arcsin}}
\renewcommand\arccos{\mathrm{Arccos}}

\renewcommand\ker{\mathrm{Ker}}
\def\im{\mathrm{Im}} %image d'un endomorphisme
\def\vect{\mathrm{Vect}} %espace engendré
\def\Mat{\mathrm{Mat}} %matrice d'une application linéaire
\def\indic{\mathbf{1}\!\mathrm{l}} %indicatrice d'un ensemble
\newcommand{\transposee}[1]{{\vphantom{#1}}^{\mathit t}{#1}} %transposée d'une matrice
\renewcommand\hat{\widehat} %mieux pour les estimateurs
\newcommand{\norme}[1]{\left\Vert {#1} \right\Vert} %norme dans un espace vectoriel
\newcommand{\valabs}[1]{\left\vert {#1} \right\vert} %valeur absolue
\newcommand{\scal}[1]{\left\langle {#1} \right\rangle} %produit scalaire
\renewcommand\epsilon{\varepsilon} %joli epsilon
\newcommand{\entiere}[1]{\left\lfloor\, {#1} \,\right\rfloor} % partie entière
\def\L{\mathcal{L}} %ensemble des fonctions intégrables
\def\M{\mathcal{M}} %ensemble de matrices
\def\equivo{\Longleftrightarrow} %double fleche d'équivalence
\def\espaceproba{(\Omega,\mathcal{A},\P )} %espace de proba omega , A ,P
\def\comp{\mathrm{c}} %complémentaire


\makeatletter

\newcommand{\noun}[1]{\textsc{#1}}

\makeatother

\setcounter{secnumdepth}{4}
\setcounter{tocdepth}{3} 
\definecolor{vert}{rgb}{0,0,0}%{0.05,0.64,0.38}
\newcommand{\imp}[1]{\textcolor{vert}{#1}}
%En tete %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\pagestyle{fancy}
\renewcommand{\chaptermark}[1]{\markboth{#1}{}}
\renewcommand{\sectionmark}[1]{\markright{ #1}}
\renewcommand{\headrulewidth}{0.1pt}
\rhead[]{\rightmark}
\lhead[\leftmark]{}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{document}
\normalem
\linespread{1.1}


\maketitle

\newpage
\strut
\thispagestyle{empty}





\newpage
\thispagestyle{empty}

\tableofcontents
\thispagestyle{empty}

\newpage
\setcounter{page}{1}




\section{Algorithme K-Means}

\subsection{Formulation du problème}

On considère un échantillon d'observations $\mathcal{X} = \{ X_1, \ldots, X_n\}$ où chaque $X_i \in \R^d$ et l'on suppose $\R^d$ muni d'une métrique quelconque $d$. L'algorithme de clustering $K$-means est un algorithme d'apprentissage non-supervisé qui vise à diviser l'échantillon $\mathcal{X}$ en $K$ partitions $S_1$, $\ldots$, $S_K$ dans lesquelles chaque observation appartient à la partition avec la moyenne la plus proche.\\

En d'autres termes on cherche à construire une partition $\mathcal{S} = (S_1, \ldots, S_K)$ de $\mathcal{X}$ qui minimise la distance entre les points à l'intérieur de chaque partition 

\[ (S_1, \ldots, S_K) = \underset{\mathcal{S}}{\mathrm{argmin}} \sum_{1 \leq i \leq K}\sum_{X_j \in S_i} d(X_j,\mu_i)\]

où $\mu_i$ pour chaque $1 \leq i \leq K$ est la moyenne des points de la partition $S_i$

\[\mu_i = \frac{1}{\vert S_i \vert} \sum_{X_j \in S_i} X_j.\]

\subsection{Description de l'algorithme}

L'initialisation de l'algorithme consiste à choisir un jeu initial de moyennes $\mu_1^{(1)}, \dots, \mu_K^{(1)}$ ce qui peut-être fait de plusieurs manières. Nous pouvons tout d'abord choisir un partitionnement aléatoire $\mathcal{S}^{(1)} = (S_1^{(1)}, \ldots, S_K^{(1)})$ de l'échantillon $\mathcal{X}$ et en déduire les moyennes correspondantes (\textsl{random partition method}) ou bien choisir aléatoirement $K$ points de l'échantillon qui seront désignés comme moyennes initiales (\textsl{forgy partition method}).\\

Supposons que l'on ait déjà effectué $T$ itérations de l'algorithme et notons $\mu_1^{(T)}, \ldots, \mu_K^{(T)}$ et $S_1^{(T)}, \ldots, S_K^{(T)}$ les moyennes et partitions correspondantes à cette itération.  On procède alors en deux étapes distinctes :

\begin{enumerate}
\item \textbf{Étape d'affectation} On assigne à chaque observation un cluster $S_i^{(T)}$ ($1 \leq i \leq K$)  dont la moyenne est la plus proche

\[ S_i^{(T)} = \left\{ X \in \mathcal{X} : X = \underset{X \in \mathcal{X}}{\mathrm{argmin}}\hspace*{0.2cm} d(X,\mu_i^{(T)})\right \}.\]
\item \textbf{Étape de mise à jour} On calcule les nouvelles moyennes $\mu_1^{(T+1)}, \ldots, \mu_K^{(T+1)}$ par 

\[ \mu_i^{(T+1)} = \frac{1}{\vert S_i^{(T)} \vert}\sum_{X_j \in S_i^{(T)}} X_j\]

pour chaque $1 \leq i \leq K$.  
\end{enumerate}

\subsection{Calcul parallèle}

Afin d'améliorer les performances de l'algorithme on peut avoir envie de faire un certain nombre de calculs en parallèle. Nos ordinateurs étant équipés de processeurs à deux coeurs, une façon naturelle d'améliorer le temps de calcul est de diviser les taches en deux parties distinctes et de faire travailler les deux coeurs en parallèle. L'algorithme de clustering des K-means est particulièrement bien adapté au calcul parallèle. \\
En effet, lors de l'étape d'affectation, on assigne à chaque individu un cluster en minimisant la distance à la moyenne. Cette tache est indépendante d'un individu à l'autre. On peut donc diviser la base de donnée en deux parties selon les individus, et effectuer l'affection des individus en parallèle avec deux threads différents. \\
Pour l'étape de mise à jour, toujours en divisant la base de donnée en deux selon les individus, on peut calculer de façon indépendante la contribution à la moyenne du groupe de chaque individu via deux threads. Voici plus précisément comment nous avons procédé:

\begin{enumerate}
\item On définit un entier $j$ égal au nombre d'individu  total, divisé par deux.

\item Étape d'affectation
\begin{itemize}
\item On définit deux threads. L'un assigne le groupe de chaque individu $X_i$ pour $i=1,..,j$. L'autre assigne le groupe de chaque individu $X_i$ pour $i=j+1,..,n$. Ici, on prend soin de ne pas recopier les sous-bases de données qui sont potentiellement très lourdes.
\item On attend que les deux threads soient finis puis on les tue. 
\end{itemize}

\item Étape de remise à zéro. 
\begin{itemize}
\item On créer un thread qui remet les moyennes et les effectifs de chaque groupe à zéro.
\item On attend que ce thread soit fini puis on le tue.

\end{itemize}

\item Étape de mise à jour. 
\begin{itemize}
\item On définit deux threads. Le premier agit sur les individus $X_i$, $i=1,..j$, le deuxième sur les individus $X_i$, $i=j+1,..,n$. Si l'individu $i$ appartient au groupe $S_k$ alors l'effectif de ce groupe est augmenté de 1. De plus, on ajoute $||X_i||$ à $\mu_k$. 
\item On attend que ces deux threads soient finis puis on les tues. 
\item On "normalise" alors les moyennes en divisant $\mu_k$ par  l'effectif du groupe $k$, pour tout $k=1,..,K$ 
\end{itemize}
\end{enumerate}

Remarquons qu'a chaque fois que nous parallélisons le calculs nous sommes obligé d'attendre que les threads soient finis avant de passer à l'étape suivante. En effet, si nous remettons les moyennes à zero avant que l'affectation de l'une des deux parties de la base soit fini, alors l'étape d'affectation sera faussée. De même, si nous lançons l'étape de mise à jour alors même que certaines moyennes ne sont pas remises à zéro, le calcul sera faux. \\

Cette remarque étant faite, attardons nous sur un autre problème inhérent au calcul parallèle: la situation de compétition. Celle-ci apparait à la fois à l'étape 2 et à l'étape 4. En effet, lors de l'affectation, nous modifions l'attribut \texttt{m$\_$Groups} qui stocke le groupe de chaque individu. Cette opération, bien que très légère, n'est pas atomique. Il est donc nécessaire de locker les lignes de codes correspondantes. \\
De la même façon, lors de l'étape de mise à jour, l'attribut \texttt{m$\_$Centroids} est modifié. Comme, cette opération est très fréquente dans les deux threads, nous pensons que locker cette partie de code reviendrait à mettre l'un des deux trheads quasiment tout le temps en file d'attente, le calcul parallèle perdrait alors tout son sens. Nous avons donc opté pour la solution suivante: 
\begin{itemize}
\item les moyennes sont localement modifiées dans chacun des deux threads via l'utilisation de la variable locale \texttt{localCentroids}.
\item une fois que le thread à fini de modifier la variable locale, il entre dans une zone critique lockée dans laquelle il peut modifier l'attribut \texttt{m$\_$Centroids}. 
\end{itemize}
Cette méthode n'est pas trop gourmande en mémoire dans la mesure où l'on suppose que le nombre de groupes est faible devant le nombre d'individus, de sorte que stoker la  variable locale \texttt{localCentroids} en plus de l'attribut \texttt{m$\_$Centroids} ne coûte pas très cher. 

\section{Structure du code}

Notre code est structuré autour de deux classes principales qui interagissent entre elles : la classe \texttt{Data} et la classe \texttt{Clustering}. Décrivons brièvement chacune de ces classes.

\begin{figure}[!h]
\center
\includegraphics[scale=0.70]{class_diagram.png}
\caption{Diagramme UML du code}
\end{figure}

\subsection{Classe \texttt{Data}}

La classe \texttt{Data} permet de donner une structure d'objet aux données que nous seront amenés à manipuler. C'est une classe qui permet de donner un type générique aux données et nous évite de manipuler des tableaux (de \texttt{double} par exemple).\\

Bien que nous ne considérons ici que des données simulées, l'avantage de cette classe est qu'elle permet une évolution du code vers des types de données autres. La classe mère \texttt{Data} est composée de trois variables membres :

\begin{itemize}
\item \texttt{m$\_$Dimension} qui représente la dimension (notée $d$ dans le paragraphe précédent) des vecteurs de notre échantillon.
\item \texttt{m$\_$Size} qui représente la taille (notée $n$ dans le paragraphe précédent) de notre échantillon.
\item \texttt{m$\_$Container} qui est une tableau bidimensionnel de nombres de type \texttt{double} qui est la représentation matricielle (de taille $n \times d$) de notre échantillon.
\end{itemize}

Il y a également des méthodes :

\begin{itemize}
\item \texttt{DisplayDataContainer} qui permet d'afficher en console le contenu des données (dans une certaine limite de taille).
\item \texttt{DisplayDataSpecs} qui permet d'afficher en console la dimension et la taille de notre échantillon.
\item \texttt{merge} qui est une méthode statique qui permet de fusionner des objets de type data (sous réserve de compatibilité dans les dimensions).
\end{itemize}

Cette classe mère générique permet d'englober les attributs et méthodes communes à tout type de données numériques réelles. Nous avons également deux classes héritées qui nous permettent de simuler les données.

\subsubsection*{La classe héritée \texttt{SimulatedUniform}}

Cette classe permet de simuler des pavés $d$-dimensionnels $[c,d]^d$ tirés uniformément. Cette classe hérite des méthodes et attributs de la classe mère \texttt{Data} et elle a deux attributs propres :

\begin{itemize}
\item \texttt{m$\_$LowerLimit} qui représente la borne inférieure $c$ du support de l'échantillon.
\item \texttt{m$\_$UpperLimit} qui représente la borne supérieure $d$ du support de l'échantillon.
\end{itemize}

Les échantillons de loi uniformes sont générés à l'aide de l'environnement \texttt{Math.NET}, plus précisement à l'aide de l'objet \texttt{MathNet.Numerics.Distributions.ContinuousUniform}.

\subsubsection*{La classe héritée \texttt{SimulatedNormal}}

Cette classe permet de simuler des échantillons gaussiens $d$-dimensionnels indépendants $\mathcal{N}(m, \sigma^ 2)$. Les attributs propres à cette classe héritée sont :

\begin{itemize}
\item \texttt{m$\_$Mean} qui représente la moyenne $m$ de l'échantillon.
\item \texttt{m$\_$StdDev} qui représente l'écart type $\sigma$ de l'échantillon.
\end{itemize}

Les échantillons gaussiens sont simulés à l'aide de l'objet \texttt{MathNet.Numerics.Distributions.Normal}.

\subsection{Classe \texttt{Clustering}}

La classe \texttt{Clustering} est une classe abstraite. Elle ne peut pas être instanciée mais elle sert de base pour ses deux classes filles \texttt{Clustering}: \texttt{ClusteringMonothread} et \texttt{ClusteringMultithread}. Comme ces deux classes ont une majorité de méthode en commun, nous avons jugé pertinent d'adopter une classe mère abstraite. La classe \texttt{Clustering} possède un certain nombre d'attributs dont les principaux sont les suivants: 

\begin{itemize}
\item \texttt{m$\_$Data}, un objet de type \texttt{Data} sur lequel agit l'algorithme de clustering.
\item De cet objet, on extrait un tableau de \texttt{double}, \texttt{m$\_$Container} qui stock les données de chaque individu et qui est plus pratique à utiliser pour les calculs. 
\item \texttt{m$\_$Groups} est un tableau d'entiers qui désigne le groupe auquel appartient chaque individu. 
\item \texttt{m$\_$Centroids} est un tableau de \texttt{double} qui stocke les coordonnées des centres de gravité de chaque individus.
\item  Enfin, on peut mentionner \texttt{m$\_$ComputationTime}, le temps de calcul qui nous permettra de comparer les performances de la classe monothredée  et de la classe multithreadée.
\end{itemize}

Pour plus de lisibilité dans notre code, chaque étape de l'algorithme de clustering est orchestré par une fonction. La méthode \texttt{LaunchAlgo} est celle qui appelle toutes les autres et les articule afin d'obtenir le résultat souhaité.\\

C'est la seule méthode qui diffère entre les classes \texttt{ClusteringMonoThreaded} et \texttt{ClusteringMultiThreaded} car c'est aussi elle qui gère les threads. Dans la classe mère, cette méthode est abstraite et on fait usage du mot clé \texttt{override} dans les classes filles. La classe \texttt{Clustering} prend en argument un objet de type \texttt{Data}, et lance l'algorithme de clustering. 

\subsubsection*{Classe héritée \texttt{ClusteringMonothreaded}}

Le constructeur de cette classe initialise les attributs en fonction des données puis appelle une première méthode \texttt{InitializeRandomCentroids} qui initialise les coordonnées des centre de gravité. Cette méthode tire au hasard des individus dans la base de donnée et les désigne comme centre de gravité initiaux en prenant soin de ne pas tirer deux fois le même individu. Une deuxième option est de choisir soi même les points de l'échantillon qui feront office de centres de gravité initiaux, via une surchage du constructeur de la classe qui prend un paramètre supplémentaire \texttt{InitialCentroids} qui est une liste d'entiers correspondants aux numéros des individus choisis.\\

La méthode \texttt{LaunchAlgo} est ensuite appelée et lance l'algorithme de clustering à proprement parler. Dans cette méthode, nous commençons par instancier une variable locale \texttt{oldGroups}, qui est un tableau d'entiers qui nous permet de vérifier le critère d'arrêt (lorsque qu'il n'y a plus de mouvement entre les clusters). Puis, tant que le critère d'arrêt n'est pas atteint, plusieurs étapes s'enchaînent:
\begin{enumerate}
\item La méthode \texttt{FindAllGroups} se charge de trouver le groupe optimal de chaque individu de la base.
 \item La méthode \texttt{ResetCentroidsSizeGroups} remet à zéro les effectifs dans chaque cluster ainsi que les coordonnées des centres de gravité. 
 \item \texttt{ComputeCentroidSizeGroups} calcule alors les cordonnées de centres de gravité ainsi que les effectifs dans chaque groups. 
 \item En réalité a ce stade, les centre de gravité ne sont pas normalisés (les moyennes ne sont pas divisées par les effectifs). Il faut donc le faire en prenant soin de ne pas diviser par un effectif nul. 
\end{enumerate}

Cette dernière étape n'appartient pas à la méthode \texttt{ComputeCentroidsSizeGroups} simplement parce que, dans la version multithread, il est plus commode d'agréger des sommes que des moyennes. 

\subsubsection*{Classe héritée \texttt{ClusteringMultiThreaded}}
La classe \texttt{ClusteringMultiThreaded} tout comme la classe \texttt{ClusteringMonothreaded} hérite de \texttt{Clustering}, de sorte que ses méthodes sont identiques, exception faite de \texttt{LaunchAlgo} qui gère le multithread. Comme évoqué plus haut, nous avons décidé de faire deux threads uniquement. 
Ainsi, \texttt{LaunchAlgo} appelle deux fois la méthode \texttt{FindAllGroups}, dans deux threads différents. Une fois les deux threads finis, elle appelle \texttt{ResetCentroidsSizeGroups} avant de lancer deux nouveaux threads appelant chacun la méthode \texttt{ThreadComputeCentroidsSizeGroups1}. A chaque fois que deux threads sont lançés, l'un agît sur la première partie de la base quand l'autre agît sur la seconde. \\

Notons que, même si cela n'est pas nécessaire pour la classe \texttt{ClusteringMonothreaded}, nous avons sécurisé les zones de code critiques dans la classe mère, et ce en utilisant un \texttt{lock} à deux endroits: 
\begin{itemize}
\item Dans la méthode \texttt{FindAllGroups}, a chaque fois que nous modifions l'attribut \texttt{m$\_$Groups}.
\item Dans la méthode \texttt{ComputeCentroidSizeGroups}, lorsque nous modifions \texttt{m$\_$SizeGroups} et  \texttt{m$\_$Centroids}. 
\end{itemize}

Notons pour terminer que la méthode \texttt{ClusteringSummary} permet d'obtenir les informations les plus importantes sur le déroulement et les résultats de l'algorithme. 


\subsection{La classe \texttt{Test$\_$clustering$\_$multithread} : tests unitaires} 
Afin de sécuriser l'algorithme de clustering, nous avons implémenté quelques tests unitaires. Nous savons qu'il existe des frameworks de tests, mais nous n'avons pas eu le temps de nous y plonger. Ainsi, nous avons créé une classe (\texttt{Test$\_$clustering$\_$multithread}) se chargeant de faire ces tests. Trois tests ont été implémenté: 
\begin{itemize}
\item \texttt{Test$\_$1$\_$obvious$\_$groups} permet de vérifier que l'algorithme trouve bien un seul groupe lorsque tous les individus sont identiques, alors que nous lui demandons de faire au plus deux groupes.
\item \texttt{Test$\_$10$\_$obvious$\_$groups()} permet de vérifier que l'algorithme trouve bien 10 groupes lorsque la base de donnée est composée de 10 individus distincts et qu'on demande de faire 10 groupes. 
\item\texttt{Test$\_$2$\_$disctinct$\_$groups()} permet de vérifier que l'algorithme trouve bien deux groupes lorsque la base de données est composée de 100 individus et 2 groupes parfaitement distincts. 
\end{itemize}

\section{Résultats numériques}
Afin de mesurer l'apport réel du calcul parallèle, nous avons comparé la performance de l'algorithme multithreadé et monothreadé. Nous avons simulé plusieurs jeux de données grâce aux classes \texttt{SimulatedNormal} et \texttt{SimulatedUniform} et lancé les deux algorithmes de clustering sur les mêmes données. Notons qu'afin de comparer ce qui est comparable nous initialisons de la même façon (et donc de façon déterministe) l'algorithme multithreadé et celui qui est monothreadé. Ceci explique l'existence \texttt{InitializeCentroids} qui prend en argument un tableau d'entier correspondant au individus qui seront choisi pour initialisé les centres de gravité. Nous avons représenté certains de nos résultats ci dessous. Dans chaque cas nous lançons l'algorithme sur 100 base de données simulées différentes. 

\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.35]{results1.pdf}
\end{center}
\caption{Boxplot du temps de calcul de l'algorithme monothreadé et multithreadé. Base de donnée:1 000 00 individus et 10 variables explicatives. Nombre de groupes: 3.  }
\end{figure}

\begin{figure}[H]
\begin{center}
\includegraphics[scale=0.35]{results2.pdf}
\end{center}
\caption{Boxplot du temps de calcul de l'algorithme monothreadé et multithreadé. Base de donnée:1 000 000 individus et 10 variables explicatives. Nombre de groupes: 2.  }
\end{figure}

Nous observons  que les gains du calcul parallèle n'est pas très conséquent. La raison précise de ce fait nous échappe pour le moment, mais deux pistes sont susceptibles d'apporter une réponse. Tout d'abord, beaucoup d'autres threads extérieurs à notre programmes (venant de d'autres applications) viennent encombrer le processeur. D'autre part, si le multithread permet de d'optimiser le temps de calcul du CPU, l'allocation de la mémoire, elle, est inchangé dans les deux cas ce qui diminue potentiellement l'impact du multithread. 


\section*{Conclusion}

Ce projet nous à permis d'apprendre beaucoup. En statistiques d'une part car nous avons découvert une première méthode d'apprentissage non supervisé, le Clustering par méthode des K-Means. Mais en informatique d'autre part, nous avons découvert la puissance du framework \texttt{.NET} avec le langage C$\#$. Enfin nous avons découvert une nouvelle approche: le calcul parallèle et une nouvelle façon de travailler en équipe l'utilisation d'un logiciel de version (Git dans notre cas) et la publication de notre source sur une page dédiée sur Google code\footnote{URL de notre projet : \texttt{https://code.google.com/p/clustering-k-means-ensae/}}. Notre principal regret est le manque de temps pour développer ce projet, nous regrettons particulièrement ne pas avoir pu traiter certaines idées dont voici deux principales :

\begin{itemize}
\item \textbf{Ajout de type de données :} il serait intéressant d'étendre nos objets \texttt{Data} à autre chose que des données simulées. Selon les applications on pourrait envisager par exemple des données de type \texttt{Image} où l'échantillon serait désormais une matrice de $n$ pixels dont chaque pixel est un vecteur de $\{0, 1, \ldots, 255\}$ (niveaux de gris) ou même $\{0, 1, \dots, 255\}^3$ (niveaux de couleur RGB). Des données type séquence d'ADN peuvent-être envisagées.
\item \textbf{Changement de métrique : } Dans notre algorithme de clustering nous utilisons la métrique euclidienne sur $\R^d$. Nous pourrions adapter le code pour prendre en compte de nouvelles métriques qui pourrait par exemple être attachée à la classe \texttt{Data} (à chaque type de donnée correspond une métrique).

\end{itemize}


\end{document}